#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <map>

string strminus(string target , string substr);

// stickers   
// target  -- string tar 
// return min num of stickers

int process(vector<string>& stickers , string target , map<string , int>& dp)
{
  if (dp.find(target) != dp.end()) 
  {
    return dp.find(target)->second;
  }

  if (target.size() == 0)
  {
    return 0;
  }

  int Min = INT32_MAX;
  for (auto first : stickers)
  {
    string rest = strminus(target , first);
    if (rest.length() != target.length())
    {
      Min = min(Min , process(stickers , rest , dp));
    }
  }

  Min = Min + (Min == INT32_MAX ? 0 : 1);
  dp[target] = Min;
  return Min;
}


string strminus(string target , string substr)
{
  int* p = new int[26];

  for (auto x : target)
  {
    p[x - 'a']++;
  }

  for (auto x : substr)
  {
    p[x - 'a']--;
  }

  string str = "";
  for (int i = 0; i < 26; i++)
  {
    while (p[i] > 0)
    {
      str += (i + 'a');
      p[i]--;
    }
  }

  return str;
}






int main()
{
  string target = "thehat";
  vector<string> v = {"with","example","science"};
  map<string , int> dp;
  cout << process(v , target , dp) << endl;
  return 0;
}
